package com.leetcode.array_matrix;

/**
 * @author Dennis Li
 * @date 2020/10/27 21:21
 */
public class Search_33 {

    public int search(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        if (nums[i] > target && nums[j] < target) return -1;
        if (nums.length == 1) return nums[0] == target ? 0 : -1;
        // 先找最小值
        while (i < j) {
            int mid = i + (j - i) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[i] == target) {
                return i;
            } else if (nums[j] == target) {
                return j;
            }
            if (nums[j] < nums[i]) {
                // i, j在不同区间
                if (nums[mid] >= nums[i]) {
                    // target在左半区
                    if (nums[mid] < target) {
                        // 在mid ~ j之间
                        i = mid + 1;
                    } else if (target > nums[i]){
                        // 在i ~ mid 之间
                        j = mid - 1;
                    } else {
                        // 在mid ~ j之间
                        i = mid + 1;
                    }
                } else if (nums[mid] <= nums[j]) {
                    //target 在右半区
                    if (nums[mid] > target)
                        j = mid - 1;
                    else if (nums[j] > target)
                        i = mid + 1;
                    else
                        j = mid - 1;
                }
            } else if (nums[i] < nums[j]) {
                // 在一个区间
                if (nums[mid] < target) {
                    i = mid + 1;
                } else {
                    j = mid - 1;
                }
            }
        }
        return -1;
    }

    public int search2(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[0] > target && nums[mid] >= nums[0]) {
                // target在左半部分并且mid在右部分
                nums[mid] = Integer.MIN_VALUE;
            } else if (nums[0] <= target && nums[mid] < nums[0]){
                // target在右半部分并且mid在左部分
                nums[mid] = Integer.MAX_VALUE;
            }

            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] > target) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return -1;
    }

    public int search3(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = i + (j - i) / 2;
            if (nums[0] > target && nums[mid] >= nums[0]) {
                // target在左半部分并且mid在右部分
                nums[mid] = Integer.MIN_VALUE;
            } else if (nums[0] <= target && nums[mid] < nums[0]){
                // target在右半部分并且mid在左部分
                nums[mid] = Integer.MAX_VALUE;
            }

            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] > target) {
                j = mid - 1;
            } else {
                i = mid + 1;
            }
        }
        return -1;
    }

}
